package leetcode_core.leetcode_1;

import java.util.LinkedHashMap;

class LRUCache {
    private LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
    int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        //将key变为最近使用
        //1.将cache中的key对应的key在删除前保存下来
        int val = cache.get(key);
        //2.删除该key
        cache.remove(key);
        //3.将该key放到链表的尾部
        cache.put(key,val);
        return val;
    }

    public void put(int key, int value) {
        //首先检查cache中是否有该key,如果有,则覆盖
        if(cache.containsKey(key)){
            cache.remove(key);
            cache.put(key,value);
            return;
        }
        //如果cache中没有该key,则先检查是否需要置换
        if(cache.size() >= this.cap){
            //此时需要置换,需要删除链表的最后一个元素
            int oldKey  = cache.keySet().iterator().next();//取到链表的头部
            cache.remove(oldKey);
        }
        cache.put(key,value);
    }
}

/**
 * Your leetocde_1.LRUCache object will be instantiated and called as such:
 * leetocde_1.LRUCache obj = new leetocde_1.LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */